package Top_Interview_Questions.Stack;

import java.util.*;

/**
 * @Author: 吕庆龙
 * @Date: 2020/1/8 9:36
 * <p>
 * 总结:
 * 1.DFS和BFS思想不仅仅用于图,它对于树也是适用的。
 * 2.DFS和BFS:  https://www.cnblogs.com/brucekun/p/8503042.html
 * 3.BFS思想暂时没看,先往后搞。复习的时候完整的搞
 */
public class _0103 {

    /**
     *      3
     *     / \
     *    9  20    <------
     *      /  \
     *     15   7  ------>
     */
    public static void main(String[] args) {
        TreeNode root = new TreeNode(3);
        TreeNode left_1 = new TreeNode(9);
        TreeNode right_1 = new TreeNode(20);
        TreeNode left_2 = new TreeNode(15);
        TreeNode right_2 = new TreeNode(7);

        root.left = left_1;
        root.right = right_1;

        right_1.left = left_2;
        right_1.right = right_2;

        zigzagLevelOrder2(root);

    }


    /**
     * DFS思想
     *
     * 执行用时 :1 ms, 在所有 Java 提交中击败了99.28%的用户
     * 内存消耗 :36.2 MB, 在所有 Java 提交中击败了40.11%的用户
     *
     * 解析:
     * 1.奇数层按从右往左放,最新的元素始终放在索引为0的地方
     * 2.偶数层按从左往右放,最新的元素始终按ArrayList的放置顺序放。
     */
    public static List<List<Integer>> zigzagLevelOrder1(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        traversal(root, res, 0);
        return res;
    }

    private static void traversal(TreeNode root, List<List<Integer>> res, int level) {
        if (root == null) {
            return;
        }

        if (res.size() == level) {
            res.add(new ArrayList<Integer>());
        }

        if ((level & 1) == 1){  //1.奇数
            res.get(level).add(0, root.val);
        } else { //2.偶数
            res.get(level).add(root.val);
        }

        traversal(root.left, res, level + 1);
        traversal(root.right, res, level + 1);
    }


    /**
     * BFS思想
     *
     * 执行用时 :1 ms, 在所有 Java 提交中击败了99.28%的用户
     * 内存消耗 :36.2 MB, 在所有 Java 提交中击败了40.11%的用户
     */
    public static List<List<Integer>> zigzagLevelOrder2(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();

        if (root == null) {
            return result;
        }

        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);

        // 统计这一层的节点数
        while (!queue.isEmpty()) {
            // 该层的节点数量
            int levelCount = queue.size();
            ArrayList<Integer> sub = new ArrayList<>();

            while (levelCount > 0) {
                TreeNode node = queue.poll();
                // 根据层次来判断顺序
                if (result.size() % 2 == 0) {
                    sub.add(node.val);
                } else {
                    sub.add(0, node.val);
                }

                if (node.left != null) {
                    queue.add(node.left);
                }
                if (node.right != null) {
                    queue.add(node.right);
                }
                levelCount--;
            }
            result.add(sub);
        }

        return result;
    }



    /**
     * 别人的题解:
     * https://leetcode-cn.com/problems/binary-tree-zigzag-level-order-traversal
     * /solution/jiao-ti-shi-yong-zhan-jian-dan-shi-xian-ju-chi-xin/
     *
     * 锯齿形遍历的意思就是
     *      3
     *     / \
     *    9  20    <------
     *      /  \
     *     15   7  ------>
     *
     * 执行结果:
     * 执行用时 :2 ms, 在所有 Java 提交中击败了24.89%的用户
     * 内存消耗 :36 MB, 在所有 Java 提交中击败了40.11%的用户
     */
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> list = new ArrayList<>();
        if (root == null) {
            return list;
        }
        //栈1来存储右节点到左节点的顺序
        Stack<TreeNode> stack1 = new Stack<>();
        //栈2来存储左节点到右节点的顺序
        Stack<TreeNode> stack2 = new Stack<>();

        //根节点入栈
        stack1.push(root);

        //每次循环中，都是一个栈为空，一个栈不为空，结束的条件两个都为空
        while (!stack1.isEmpty() || !stack2.isEmpty()) {
            List<Integer> subList = new ArrayList<>(); // 存储这一个层的数据
            TreeNode cur = null;

            if (!stack1.isEmpty()) { //栈1不为空，则栈2此时为空，需要用栈2来存储从下一层从左到右的顺序
                while (!stack1.isEmpty()) {    //遍历栈1中所有元素，即当前层的所有元素
                    cur = stack1.pop();
                    subList.add(cur.val);    //存储当前层所有元素

                    if (cur.left != null) //左节点不为空加入下一层
                        stack2.push(cur.left);
                    if (cur.right != null)    //右节点不为空加入下一层
                        stack2.push(cur.right);

                }
                list.add(subList);
            } else {//栈2不为空，则栈1此时为空，需要用栈1来存储从下一层从右到左的顺序
                while (!stack2.isEmpty()) {
                    cur = stack2.pop();
                    subList.add(cur.val);

                    if (cur.right != null) //右节点不为空加入下一层
                        stack1.push(cur.right);
                    if (cur.left != null)  //左节点不为空加入下一层
                        stack1.push(cur.left);
                }
                list.add(subList);
            }
        }
        return list;
    }

}
